package org.example.leetcode;

import java.util.Arrays;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:   最接近的三数之和
 * @date: 2021/7/25 21:39
 */
public class LC16 {
    public static void main(String[] args) {

    }

    //fixme https://www.bilibili.com/video/BV1NK411T784?from=search&seid=17090547926577927051
    public int threeSumClosest(int[] nums, int target) {
        int diff=Integer.MAX_VALUE;
        int res=0;
        Arrays.sort(nums); //fixme 排序后
        for (int k=0; k<nums.length-2;k++){
            if (k>0 && nums[k]==nums[k-1]) continue;
            int start=k+1;int end=nums.length-1;
            while (start<end){
                int sum= nums[k]+nums[start]+nums[end];
                if (sum==target){
                    return target;
                }else if (sum<target){
                    start++;
                }else if (sum>target){
                    end--;
                }
                int tmpDiff=Math.abs(sum-target);
                if (tmpDiff<diff){
                    //更新值
                    diff=tmpDiff;
                    res=sum;
                }

            }
        }
        return  res;
    }
}
